package hanjia;

import java.util.ArrayList;
import java.util.List;

/**
 * Description:
 * Author:    Dane
 * CreateTime:2025/2/13-下午8:14
 * Since  :   1.0
 * Version:   1.0
 */
public class LeetCode216 {

    public List<List<Integer>> combinationSum3(int k, int n) {
        int start=1;
        List<Integer> result = new ArrayList<>();
        List<List<Integer>> results=new ArrayList<>();

         backtracking(start,n,k,result,results);
         return results;

    }

    private void backtracking(int start, int n, int k, List<Integer> result, List<List<Integer>> results) {

        if (sum(result)>n){
            return;
        }

        if (result.size()==k){
            if (sum(result)==n){
                results.add(new ArrayList<>(result));
            }
            return;
        }

        for (int i=start;i<=9;i++){
            result.add(i);
            backtracking(i+1,n,k,result,results);
            result.remove(result.size()-1);
        }


    }

    private int sum(List<Integer> result){
        int sum=0;
        for (int i:result){
            sum+=i;
        }
        return sum;
    }

}
